package test1;

import java.util.*;
import java.util.List;

/**
 * 计算布尔二叉树的值
 */
public class Main7 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public boolean evaluateTree(TreeNode root) {
        if(root.left == null) return root.val == 0 ? false : true;

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : left & right;
    }

    /**
     * 求根节点到叶节点数字之和
     * @param root
     * @return
     */

    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    public int dfs(TreeNode root, int preSum) {
        preSum = preSum * 10 + root.val;
        if(root.left == null && root.right == null) {
            return preSum;
        }
        int ret = 0;
        if(root.left != null) {
            ret += dfs(root.left, preSum);
        }
        if(root.right != null) {
            ret += dfs(root.right, preSum);
        }
        return ret;
    }

    /**
     * 二叉树剪枝
     * @param root
     * @return
     */

    public TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0) {
            root = null;
        }
        return root;
    }


    /**
     * 验证二叉搜索树
     */
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        boolean left = isValidBST(root.left);
        if(left == false) return false;

        boolean cur = false;
        if(prev < root.val) {
            cur = true;
        }

        if(cur == false) return false;
        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && cur && right;
    }

    /**
     * 二叉搜索树中第K小的元素
     */

    int count;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    public void dfs(TreeNode root) {
        if(root == null || count == 0) {
            return;
        }
        dfs(root.left);
        count--;
        if(count == 0) {
            ret = root.val;
            return;
        }
        dfs(root.right);
    }

    /**
     * 二叉树的所有路径
     */

    List<String> ret1;
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        StringBuffer path;
        dfs(root, new StringBuffer());
        return ret1;
    }
    public void dfs(TreeNode root, StringBuffer _path) {
        StringBuffer path = new StringBuffer(_path);
        path.append(Integer.toString(root.val));
        if(root.left == null && root.right == null) {
            ret1.add(path.toString());
            return;
        }
        path.append("->");
        if(root.left != null) dfs(root.left, path);
        if(root.right != null) dfs(root.right, path);
    }
}
